package anthology.daily_question._24_12;
//https://leetcode.cn/problems/knight-dialer/description/?envType=daily-question&envId=2024-12-10
public class _0935骑士拨号器 {
    class Solution {
        private static final int MOD = 1_000_000_007;
        private static final int[][] NEXT = {
                {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}
        };
        private static final int[][] memo = new int[5000][10];

        public int knightDialer(int n) {
            if (n == 1) {
                return 10;
            }
            int ans = 0;
            for (int j = 0; j < 10; j++) {
                ans = (ans + dfs(n - 1, j)) % MOD;
            }
            return ans;
        }

        private int dfs(int i, int j) {
            if (i == 0) {
                return 1;
            }
            if (memo[i][j] > 0) { // 之前计算过
                return memo[i][j];
            }
            int res = 0;
            for (int k : NEXT[j]) {
                res = (res + dfs(i - 1, k)) % MOD;
            }
            return memo[i][j] = res; // 记忆化
        }
    }

    class Solution2 {
        private static final int MOD = 1_000_000_007;
        private static final long[][] memo = new long[5000][10];

        public int knightDialer(int n) {
            if (n == 1) {
                return 10;
            }
            return (int) ((dfs(n - 1, 0) * 4 + dfs(n - 1, 1) * 2 +
                    dfs(n - 1, 2) * 2 + dfs(n - 1, 3)) % MOD);
        }

        private long dfs(int i, int j) {
            if (i == 0) {
                return 1;
            }
            if (memo[i][j] > 0) { // 之前计算过
                return memo[i][j];
            }
            if (j == 0) {
                memo[i][j] = (dfs(i - 1, 1) + dfs(i - 1, 2)) % MOD;
            } else if (j == 1) {
                memo[i][j] = dfs(i - 1, 0) * 2 % MOD;
            } else if (j == 2) {
                memo[i][j] = (dfs(i - 1, 0) * 2 + dfs(i - 1, 3)) % MOD;
            } else {
                memo[i][j] = dfs(i - 1, 2) * 2 % MOD;
            }
            return memo[i][j];
        }
    }
}
